/**
 * 
 */
package it.uniroma3.dia.digraph.algorithm.path;

import it.uniroma3.dia.digraph.algorithm.Algorithm;
import it.uniroma3.dia.digraph.algorithm.utility.Utility;

import java.awt.Point;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.graphdrawing.graphml.xmlns.EdgeType;
import org.graphdrawing.graphml.xmlns.GraphType;
import org.graphdrawing.graphml.xmlns.NodeType;

/**
 * @author BarycentricCoords
 *
 */
public class LinearizePath extends Algorithm {

	private Map<String, Set<String>> adjacencyList;

	@Override
	public void apply(GraphType... inputGraphs) {

		//polite program say "hello!"
//		System.out.println("Have a break, let me morph!");

		if (inputGraphs.length!=1)
			throw new InputMismatchException("input size must be 1");

		this.init(inputGraphs);		
			
		
		//align nodes
		alignNodes(this.sortNodes(), inputGraphs[0].getEdgeCollection().getEdge());

//		System.out.println("bye bye!");
	}








	/**
	 * Aligns the nodes on the path represented by "nodes" and "edges"
	 * @param nodes a (sorted) list of the nodes on the path to align
	 * @param edges a list of the edges of the path to align
	 */
	private void alignNodes(List<NodeType> nodes, List<EdgeType> edges){

		Point2D point;		
		nodes.get(0).setDefault(false);
		for (int i=1; i<nodes.size()-1;i++){
			if (!isAligned(nodes.get(i), nodes.get(i-1), nodes.get(i+1))){
				
				point = this.findSpannableTriangleVertex(nodes.get(i), nodes, edges);			
				nodes.get(i).setDefault(false);			
				this.move(i, nodes, point);					
			}
			
			this.updateView();
			nodes.get(i).setDefault(true);
		}		
	}

	private boolean isAligned(NodeType current, NodeType a,
			NodeType b) {
		
//		System.out.println("checking: "+current.getId()+" on "+a.getId()+" "+b.getId()+": "+(Line2D.Double.ptLineDist(a.getX(), a.getY(), b.getX(), b.getY(), current.getX(), current.getY()))+"vs"+Double.MIN_VALUE);
		return Line2D.Double.ptLineDist(a.getX(), a.getY(), b.getX(), b.getY(), current.getX(), current.getY()) == 0;
	}








	/**
	 * Find a triangle spannable by nodes 1...current-1
	 * @param current a vertex of the triangle
	 * @param nodes the nodes of this path
	 * @param edges the edges of the path
	 * @return
	 */
	private Point findSpannableTriangleVertex(NodeType current,
			List<NodeType> nodes, List<EdgeType> edges) {

		double dist;
		Point point;		
		dist = Utility.distance(nodes.get(0), current);
		
		dist = Math.min(dist, 200);
		
		point = Utility.getPointOnProlung(nodes.get(nodes.indexOf(current)+1), current, dist);

		while(! Utility.isTspannable(nodes.get(0), current, point, edges, nodes, this.getIdToNodes())){
			//triangle is not spannable... make it smaller
			dist = dist * 0.75;		
			point = Utility.getPointOnProlung(nodes.get(nodes.indexOf(current)+1), current, dist);
		}	

		return point;
	}




	/**
	 * Sorts the nodes on this path, the first and the last have degree 1
	 * @return a sorted list of the nodes on this path
	 */
	private List<NodeType> sortNodes() {
		List<NodeType> result = new LinkedList<NodeType>();
		NodeType current = this.findSource();
		while (current!=null){
			result.add(current);
			current = this.findNext(current.getId());
		}				
		return result;
	}

	/**
	 * Finds next node on the path
	 * @param currentId the id of the current node
	 * @return the next node on the path
	 */
	private NodeType findNext(String currentId) {
		Set<String> idSet = this.adjacencyList.get(currentId);

		if (idSet!=null && !idSet.isEmpty()){ //the set contains just one string
			String nextId = this.adjacencyList.get(currentId).iterator().next();
			this.adjacencyList.remove(currentId);
			this.adjacencyList.get(nextId).remove(currentId);

			return this.getIdToNodes().get(nextId);
		}		
		return null;
	}

	/**
	 * Returns the source of an undirected path: a node whose degree is one
	 * @param nodes a list containing the nodes
	 * @return the source of an undirected path: a node whose degree is one
	 */
	private NodeType findSource() {
		for (String id : this.adjacencyList.keySet()){
			if(adjacencyList.get(id).size()==1)
				return this.getIdToNodes().get(id);
		}		
		return null;
	}


	/**
	 * Moves first k nodes on the ray passing trough node k and "point" 
	 * @param k the number of the nodes to align
	 * @param nodes a (sorted) list of nodes representing the path
	 * @param point the end point of the segment
	 */
	private void move(int k, List<NodeType> nodes, Point2D point) {
		double distance = Utility.distance(nodes.get(0), point);
		double step = distance/k;
		double sourceCoeff, endCoeff;

		for (int i=0; i<k;i++){

			sourceCoeff = (i*step)/distance;
			endCoeff = (distance - (i*step))/distance;
			nodes.get(i).setX((sourceCoeff*nodes.get(k).getX() + endCoeff*point.getX()));
			nodes.get(i).setY((sourceCoeff*nodes.get(k).getY() + endCoeff*point.getY()));		

		}

	}

	@Override
	protected void init(GraphType... inputGraphs) {
		// "standard" initialisation
		this.setGraph(inputGraphs[0]);
		this.setIdToNodes(Utility.extractNodes(inputGraphs[0]));
		this.setEdgeList(inputGraphs[0].getEdgeCollection().getEdge());		

		// "custom" initialisation
		this.adjacencyList = Utility.buildAdjacencyMatrix(inputGraphs[0]);
	}








	@Override
	public void checkInput(GraphType[] inputGraphs)
			throws InputMismatchException {
		// TODO Auto-generated method stub
		
	}


}
